package com.caoyanan.algorithm.question.zuoTraining.training004.class02;

import com.caoyanan.algorithm.question.zuoTraining.LogarithmInputGenerator;

import java.util.Arrays;
import java.util.HashSet;

/**
 * 假设所有字符都是小写字母.   长字符串是str
 * arr是去重的单词表, 每个单词都不是空字符串且可以使用任意次
 * 使用arr中的单词有多少种拼接str的方式，返回方法数.
 * @author: caoyanan
 * @time: 2021/6/15 23:49
 */
public class Question04_StringSplicing {

    public static void main(String[] args) {

        int count = 10000;
        for (int i = 0; i < count; i++) {
            String str = LogarithmInputGenerator.getInstance()
                    .generateLowerLetterString(10, 3);
            String[] arr = {"a", "b", "c", "ac", "ab", "bc"};
            int answer1 = violenceMethod(str, arr);
            int answer2 = trieTreeMethod(str, arr);
            if (answer1 != answer2) {
                System.out.printf("字符串: %s ，单词表: %s ，暴力方法拼接方法数为: %s, 前缀树拼接数为: %s \n",
                        str, Arrays.toString(arr), answer1, answer2);
            }
        }
        /**
         * 这道题code失误， arr 和char 用混 、 i--和i++写混等等
         */
    }

    public static class TrieNode {

        public int pass;
        public int end;
        public TrieNode[] nexts;

        public TrieNode() {
            pass = 0;
            end = 0;
            nexts = new TrieNode[26];
        }
    }
    /**
     * 所有字符都是小写字母，而且要判断[i...j]每个位置的前缀串是否存在，
     * 所以，非常适合使用前缀树结构
     * @param str
     * @param arr
     * @return
     */
    private static int trieTreeMethod(String str, String[] arr) {

        TrieNode head = new TrieNode();
        for (int i = 0; i < arr.length; i++) {
            fillInTrieTree(head, arr[i]);
        }

        char[] chars = str.toCharArray();
        int[] dp = new int[chars.length + 1];
        dp[chars.length] = 1;
        for (int i = chars.length - 1; i >= 0; i--) {
            TrieNode node = head;
            int currentPositionCount = 0;

            for (int j = i; j < chars.length; j++) {
                int index = chars[j] - 'a';
                // 如果一个字符断了，后续的都不需要看了，因为前缀树，要想有整体的，前面的一个都不能缺
                if (node.nexts[index] == null) {
                    break;
                }
                currentPositionCount += dp[j+1];
                node = node.nexts[index];
            }
            dp[i] = currentPositionCount;
        }
        return dp[0];
    }

    private static void fillInTrieTree(TrieNode head, String str) {
        TrieNode node = head;
        char[] chars = str.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            int index = chars[i] - 'a';
            TrieNode next = node.nexts[index];
            if (next == null) {
                node.pass++;
                node.nexts[index] = new TrieNode();
                next = node.nexts[index];
            }
            node = next;
        }
        node.end ++;
    }

    /**
     * dp[i] 表示 str[i...end]子串有多少种拼接方式
     * 这个是不是从左往右的尝试模型，应该属于的。
     * 回忆一下动态规划的常见模型，从左到右的尝试模型(背包), 一个样本做行一个样本做列的对应模型(一个字符串的多少种子序列等于另一个字符串)
     *              范围的尝试模型， 业务限制模型
     * 然后对于一个普遍位置dp[i]
     * 依次遍历所有前缀是否存在  str[i...j]存在吗 ? dp[j+1] : 0
     *
     * 这个暴力方法一般认为复杂度是O(n^3)，此时哈希表是否包含认为是O(n)的3次方，字符串的长度不能忽视了
     * @param str
     * @param arr
     * @return
     */
    private static int violenceMethod(String str, String[] arr) {

        char[] chars = str.toCharArray();
        HashSet<String> set = new HashSet<>();
        for (int i = 0; i < arr.length; i++) {
            set.add(arr[i]);
        }

        int[] dp = new int[chars.length+1];
        // 为什么是1而不是0， 比如 "....ab", 存在 "ab"的单词 ，那么 dp[arr.length-2] = ab存在吗 ?  dp[arr.length] : 0;即要有一个初始因子，不然整张表填完之后都是0
        dp[chars.length] = 1;
        for (int i = chars.length - 1; i >= 0; i--) {
            // 当前的拼接方式
            int current = 0;
            String prefix = "";
            for (int j = i; j < chars.length; j++) {
                prefix = prefix + chars[j];
                current += set.contains(prefix) ? dp[j+1] : 0;
            }
            dp[i] = current;
        }
        return dp[0];
    }
}
